1. Field of the Invention
The present invention relates to a constant multiplier for multiplying a constant by a signal set to an optional value, a method and a device for automatically providing such a constant multiplier and a storage medium storing a program used for automatically providing such a constant multiplier.
2. Description of the Related Art
Generally, a large scale application specific integrated circuit (ASIC) having functions of a moving picture expert group (MPEG), and so on, needs a number of multipliers each as an arithmetic circuit for performing image processing or the like. Most of these multipliers multiply constants (already known fixed numbers) by signals having unknown optional values.
For example, multiplication of a constant by a signal is often used for discrete cosine/color space transformation. Specifically, in a RGB code/YUV code conversion expression like that described below, U and V are signals having unknown optional values and parameters (coefficients) multiplied by these signals U and V are constants. EQU R=Y+1.367.times.V EQU G=Y-0.703125.times.U-0.34375.times.V EQU B=Y+1.7345.times.U
Conventionally, multipliers for multiplying constants by signals like those described above have been designed not as special multipliers for the constants but as multipliers for multiplying unknown optional values by each other. In other words, multiplication of a constant by a signal is performed by a multiplier operated based on the same algorithm as that for performing multiplication of a signal by another signal.
It can thus be understood that conventionally, for designing of a large scale integrated circuit, even if a value for one of signals to be multiplied by each other is fixed and known beforehand, the signal (constant) has been treated as a signal having an unknown value and no optimization has been carried out for a circuit as a constituting element for the multiplier.
Consequently, in the large scale integrated circuit (e.g., LSI for MPEG) having a number of useless circuit portions and a number of multipliers for multiplying constants by signals, if a multiplier like that described above is formed, not only an area for the circuit is increased but also operational delay is caused to occur.
For example, a multiplier designed by using a shift multiplier method treats a multiplier B which is a constant as a signal and produces a partial product from a product with a multiplicand A for each figure (bit), and the partial products thus obtained for respective bits are shifted each by 1 bit and added together. Specifically, with A="1101" and B="1011", calculation is performed in a manner described below.
1101 Multiplicand (A: signal) .times. 1011 Multiplier (B: constant) 1101 Partial product1 (A) 1101 Partial product2 (2A) 0000 Partial product3 (0) + 1101 Partial product4 (8A) 10001111 Multiplication result
In the above example, since the partial product 3 is 0, this product need not be added in actuality. However, if a multiplier for multiplying a signal by another signal is used, the partial product 3 is also added and accordingly an unnecessary circuit (adder) is provided.
Next, the circuitry example of the multiplier designed by producing partial products with the shift multiplier method will be described by referring to FIGS. 11 and 12.
Referring first to FIG. 11, there are shown a multiplication processing procedure and a constitutional example of a multiplier. It is assumed that as a multiplier, for instance a constant "59 [=(111011).sub.2 ; 6 bits ]" is given and a multiplicand is a signal A. In this case, if partial products are to be produced by using the above-noted shift multiplier method, six partial products 6 32A, 5 16A, 4 8A, 3 0A, 2 2A and 1 A are obtained. A partial product adding circuit, in other words a multiplier 100, for calculating a multiplication result "59A" with the signal A by adding these products together to output it, is then provided.
The multiplier 100 shown in FIG. 11 is constructed in a manner that five carry save adders (abbreviated to CSA, hereinafter) 101 to 105 are connected together and a carry look-ahead adder (abbreviated to CLA, hereinafter) 106 which is a typical high-speed type carry propagate adder (abbreviated to CPA, hereinafter) is connected to a stage next to the CSA 105 as a last stage. For an adder used in the last stage, any type may be used as long as it belongs to CPA. For example, a carry select adder or a ripple carry adder other than CLA can be used.
In the multiplier constructed in the above-noted manner, multiplication processing is performed as follows. The partial products 6, 5, 4, 3, 2 and 1 are regularly added together in sequence by the five CSAs 101 to 105, carried values are propagated at a high speed and added together by the CLA 106 in the last stage and then a multiplication result "59A" is outputted. In the multiplier 100 shown in FIG. 11, the number of adding stages excluding the last stage is "5".
However, since the multiplier 100 is designed without making any determination as to whether the partial product is "0" or not, the CSA 103 for adding the partial product 3 which is "0" must be provided. Consequently, a circuit area is increased and operational delay is caused to occur.
Referring next to FIG. 12, there is shown a procedure for designing a constant multiplier and a constitutional example thereof. A multiplier 200 shown in FIG. 12 produces six partial products 1 to 6 by using the same shift multiplier method as that shown in FIG. 11, adds these six partial products 6, 5, 4, 3, 2 and 1 together and thereby calculates a multiplication result "59A". In this case, the multiplier 200 comprises four CSAs 201 to 204 interconnected in a tree form so as to reduce the number of adding stages and a CPA 205 connected to a stage next to the CSA 204 as a last stage. In other words, the constant multiplier 200 having adding stages amounting in number to "3" is provided/designed by the four CSAs 201 to 204. This tree-formed adder construction is called "Wallace tree". For the CPA 205, a CLA or a carry select adder can be used.
With the multiplier 200 provided/designed in the above-noted manner, since the number of adding stages can be reduced compared with the case of the multiplier 100 shown in FIG. 11 and the number of CSAs to be used can also be reduced, the problems of an increased circuit area and operational delay may be solved to a certain extent. However, the number of adding stages and the number of used adders should preferably be reduced much more.
Referring further to FIG. 13, there is shown another constitutional example of a multiplier. A multiplier 300 shown in FIG. 13 comprises a partial product generation circuit, which includes a booth decoder 301 and a booth selector 302. By using this partial product generation circuit, the number of partial products can be reduced by half. Accordingly, when a constant "59" is to be multiplied by a signal A as described above, the number of partial products is reduced from six to three, the three partial products 1 to 3 are added together by an adding circuit (by "Wallace tree" or CSA) 303 and a CLA 304 in the last stage and then a multiplication result "59A" is calculated.
With the multiplier 300 constructed in the above-noted manner, since the booth decoder 301 and the booth selector 302 are formed, extra hardware must be provided. Consequently, the problems of an increased circuit area and operational delay cannot be solved.